package com.dmall.graph.bfs.app;

import java.util.*;

// 使用一个5L的杯子和3L的杯子如何得到4L的水
public class WaterPuzzle {

    private int dest = -1;
    private int[] dis = new int[54];

    public WaterPuzzle() {
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[54];
        queue.add(0);
        visited[0] = true;
        while (!queue.isEmpty()) {
            int cur = queue.remove();
            for (int next : getNexts(cur)) {
                if (!visited[next]) {
                    queue.add(next);
                    visited[next] = true;
                    dis[next] = cur;
                    if (next % 10 == 4 || next / 10 == 4) {
                        dest = next;
                        return;
                    }
                }
            }
        }
    }

    private List<Integer> getNexts(int cur) {
        List<Integer> list = new ArrayList<>();
        int x = cur / 10;
        int y = cur % 10;
        list.add(x * 10);
        list.add(y);
        list.add(5 * 10 + y);
        list.add(x * 10 + 3);
        // x桶的水倒给y桶的水
        int nextx = x > (3 - y) ? x + y - 3 : 0;
        int nexty = x > (3 - y) ? 3 : x + y;
        list.add(nextx * 10 + nexty);
        // y桶的水倒给x桶的水
        nextx = y > (5 - x) ? 5 : x + y;
        nexty = y > (5 - x) ? x + y - 5 : 0;
        list.add(nextx * 10 + nexty);
        return list;
    }

    public Iterable<Integer> results() {
        ArrayList<Integer> res = new ArrayList<>();
        if (dest == -1) {
            return res;
        }
        int cur = dest;
        while (cur != 0) {
            res.add(cur);
            cur = dis[cur];
        }
        res.add(0);
        Collections.reverse(res);
        return res;
    }

    public static void main(String[] args) {
        WaterPuzzle waterPuzzle = new WaterPuzzle();
        Iterable<Integer> results = waterPuzzle.results();
        for (Integer result : results) {
            System.out.print(String.format("%02d", result) + " ");
        }
        System.out.println();
    }
}
